The present invention relates to scheduling of tasks in a computing device, such as a printing device and, more particularly, to allocating processing resources in a computing device to tasks in a manner that ensures substantially seamless processing of an active job while preventing starvation of background tasks.
Conventional operating systems for computing devices, such as printing devices, typically schedule tasks based on strict priority and schedule tasks at the some priority round-robin. Under this scheduling algorithm, background tasks, such as background print spooling tasks, typically receive little processing time because they have a lower priority than active job tasks. If the priority assignment of the background tasks were raised to the same level as the active job tasks (or, conversely, if the priority assignment of the active job tasks were lowered to the some level as the background tasks), the background tasks would receive abundant processing time but would interfere too much with the active job.
Some operating systems used in computing devices have introduced scheduling algorithms that allocate a specified block of processing time to a task upon creation of the task. While these scheduling algorithms can guarantee that a background task will not be starved-out, they suffer from other problems. First, these allocations generally cannot be reduced if the processor becomes oversubscribed. For example, if a second background spooling task is created while a first background spooling task is still pending, these algorithms will generally allocate the same amount of processing time to the second task as to the first, resulting in twice as much processing time being allocated to background spooling and too much interference with an active job. Second, these allocations are generally monolithic in their use of processing time. That is, once a background task starts to run it will claim the processor for the entire duration of the allocated block of processing time. This can lead to a sustained interruption in processing of an active job that is noticeable (e.g. “jerky” execution) and too lengthy from a user's perspective.